package com.lzq.leetcode.dp;

import java.util.Arrays;

public class s647 {

    public static int countSubstrings(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        int[][] dp = new int[n][n];
        for (int i=0; i<n; i++) {
            dp[i][i] = 1;
        }
        // 统计其他
        for (int i=n-1; i>=0; i--) {
            for (int j=i+1; j<n; j++) {
                if (cs[i] == cs[j]) {
                    if ( i-1 >= 0 && j+1 <n && j-i>2 ) {
                        dp[i][j] = dp[i+1][j-1];
                    } else {
                        dp[i][j] = 1;
                    }
                }

            }
        }


        return Arrays.stream(dp).flatMapToInt(Arrays::stream).sum();
    }

    public static void main(String[] args) {
        System.out.println(countSubstrings("aaaaaa"));
    }
}
